/**
 * @Author: linzp
 * @Date: 2021/12/08/16:35
 */
public class solution72 {

}

/**
 * medium
 * 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
 *
 * 给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
 *
 * 输入：[1,2,3,1]
 * 输出：4
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/house-robber
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution198 {
    public static void main(String[] args) {
        int[] a={1,2,3};
        System.out.println(rob(a));
    }

    public static int rob(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);//“当前偷到当前房子为止的最大金额”
        }
        return dp[n];
    }



    public int rob3(int[] nums) {
        int prev = 0;
        int curr = 0;

        // 每次循环，计算“偷到当前房子为止的最大金额”
        for (int i : nums) {
            // 循环开始时，curr 表示 dp[k-1]，prev 表示 dp[k-2]
            // dp[k] = max{ dp[k-1], dp[k-2] + i }
            int temp = Math.max(curr, prev + i);
            prev = curr;
            curr = temp;
            // 循环结束时，curr 表示 dp[k]，prev 表示 dp[k-1]
        }

        return curr;
    }

    /**
     * 413. 等差数列划分
     * 如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。
     *
     * 例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
     * 给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。
     *
     * 子数组 是数组中的一个连续序列。
     * 输入：nums = [1,2,3,4]
     * 输出：3
     * 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。
     */
    class Solution413 {
        public int numberOfArithmeticSlices(int[] nums) {
            int n = nums.length;
            if (n == 0 || n == 1 || n == 2) {
                return 0;
            }
            int dp = 0, ans = 0;
            for (int i = 2; i < n; i++) {
                if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                    dp = dp + 1;
                } else {
                    dp = 0;
                }
                ans += dp;
            }
            return ans;

        }
    }
/*
* 动态规划

思路：

定义状态 dp[i] : 以 nums[ i ] 结尾的等差子数列的个数， 对 dp[ i ] ( 0 <= i < n ) 求和 就得到 nums 中 等差数列的总的个数；

状态初始化 ： 由于题目要求的等差数列长度不能小于3 ，dp[ 0 ] = 0, dp [ 1 ] = 0;

状态转移方程 ： 举栗子 nums = [1,2,3,4,5,7 ] , dp[0] = 0, dp[1] = 0, 对 dp[2] , nums[2] - nums[1] == nums[1] - nums[0] , dp[2] = dp[1] + 1 = 0 + 1; dp[2] 相对于 dp[1] 多了一个以 nums[2] 结尾的 [1,2,3] 对 dp[3] , nums[3] - nums[2] ==nums[2] - nums[1] , dp[3] = dp[2] + 1 = 0 + 1; dp[3] 相对于 dp[2] 多了一个以 nums[] 结尾的 [2,3,4]; . . . 对 dp[5] , nums[5] - nums[4] != nums[4] - nums[3] , dp[5] = 0;

dp[i] = nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ? dp[i-1] + 1 : 0;

因为 dp [i] 只和 dp[i-1] 有关， 所以使用一个变量记录状态转移就可以了。

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        const int n = nums.size();
        int dp = 0;
        int ans = 0;
        for(int i = 2; i < n; ++i){
            dp = nums[i] - nums[i-1] == nums[i-1] - nums[i-2] ? dp + 1 : 0;
            ans += dp;
        }
        return ans;
    }
};*/
}
